package JZ;

import java.util.*;

public class jz36 {
    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    static TreeNode pre = null;
    public static void main(String[] args) {
            Convert(null);
    }
    public static TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null)
                return null;
            List<TreeNode> list = new ArrayList<>();
            back(pRootOfTree, list);
            TreeNode re = list.get(0);
            re.left = null;
        for (int i = 0; i < list.size() - 1; i++) {
            TreeNode p = list.get(i);
            TreeNode q = list.get(i + 1);
            p.right = q;
            q.left = p;
        }
        list.get(list.size() - 1).right = null;
        return re;
    }
    public static void back(TreeNode p, List<TreeNode> list){
            if(p != null){
                back(p.left,list);
                list.add(p);
                back(p.right, list);
            }
    }

    public static TreeNode Convert1(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            return null;
        TreeNode re = pRootOfTree;
        while(re.left != null)
            re = re.left;
        back2(pRootOfTree);
        return re;
    }
    public static void back2(TreeNode p){
        if(p != null){
            back2(p.left);
            p.left = pre;
            if(pre != null)
               pre.right = p;
            pre = p;
            back2(p.right);
        }
    }
}
